//
// Created by Administrator on 2022/2/4.
//

#ifndef CPP_LEARNING_LEETCODE117_H
#define CPP_LEARNING_LEETCODE117_H
#include<iostream>
#include<vector>
using namespace std;
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
            : val(_val), left(_left), right(_right), next(_next) {}
};
class Solution {
public:
    Node* connect(Node* root) {

        vector<Node*> nodeLists;
        if(root){
            nodeLists.push_back(root);
            connectHelper(nodeLists);
        }
        return root;
    }

    // [l,r]
    void connectHelper(vector<Node*>& nodeLists){
        if(nodeLists.empty()) return;
        for(int i=0;i<nodeLists.size()-1; i++){
            nodeLists[i]->next = nodeLists[i+1];
        }
        nodeLists[nodeLists.size()-1]->next = nullptr;

        vector<Node*> childNodeLists;
        for(int i=0;i<nodeLists.size(); i++){
            if(nodeLists[i]->left){
                childNodeLists.push_back(nodeLists[i]->left);
            }
            if(nodeLists[i]->right){
                childNodeLists.push_back(nodeLists[i]->right);
            }
        }
        connectHelper(childNodeLists);
    }
};
#endif //CPP_LEARNING_LEETCODE117_H
